package com.brett.frame.learn.sort.choose;

import com.brett.frame.learn.sort.base.BaseSort;
import com.brett.frame.learn.sort.base.Sort;

/**
 * 直接选择排序
 * 从待排序列中选择最小的一个，放在已有升序列尾部
 * {@link https://www.cnblogs.com/shen-hua/p/5424059.html}
 * @author lenovo
 *
 */
public class DirectChooseSort extends BaseSort implements Sort {

	@Override
	public int[] sort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[i]) {
					super.exchange(arr, i, j);
				}
			}
		}
		return arr;
	}

	/**
	 * 减少交换次数
	 * @param arr
	 * @return
	 */
	public int[] sortByIndex(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int k = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[k]) {
					k = j;
				}
			}
			if (k != i) {
				super.exchange(arr, i, k);
			}
		}
		return arr;
	}
}
